import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

// 最大频率栈
// 测试链接 : https://leetcode.cn/problems/maximum-frequency-stack/
public class MaximumFrequencyStack {

    class FreqStack {

        public int topTimes;   //记录最大词频
        public HashMap<Integer, ArrayList<Integer>>  map; //每层的结点

        public HashMap<Integer,Integer> valueTimes;  //词频表，记录每个数出现的次数

        public FreqStack() {
            topTimes = 0;
            map = new HashMap<>();
            valueTimes = new HashMap<>();
        }

        public void push(int val) {
            int times =valueTimes.getOrDefault(val,0) + 1;  //当前数的词频
            valueTimes.put(val,times);

            if(!map.containsKey(times)) {
                ArrayList<Integer> arr = new ArrayList<>();
                arr.add(val);
                map.put(times,arr);
            }else {
                map.get(times).add(val);
            }

            topTimes = Math.max(times,topTimes);  //记录当前最大词频
        }

        public int pop() {
            ArrayList<Integer> arr = map.get(topTimes);
            int ans = arr.get(arr.size()-1);  //获取最顶层数组中最右边的数
            valueTimes.put(ans,valueTimes.get(ans)-1); //词频表对应数里的词频减去1
            if(valueTimes.get(ans) == 0){
                valueTimes.remove(ans);
            }

            arr.remove(arr.size()-1);
            if(arr.isEmpty()){
                map.remove(topTimes);
                topTimes--;
            }
            return ans;
        }
    }
}
